#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/11/12 11:11
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 中级-二叉树的序列化与反序列化.py
# @Software: PyCharm

# Definition for a binary tree node.


class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if root is None:
            return '[]'
        data = [str(root.val)]
        que = [root]
        while que:
            new_que = []
            for x in que:
                if x:
                    new_que.append(x.left)
                    new_que.append(x.right)
                    data.append(str(x.left.val) if x.left else 'null')
                    data.append(str(x.right.val) if x.right else 'null')
            que = new_que
        dl = len(data)
        while data[dl - 1] == 'null' or data[dl - 1] is None:
            data.pop(dl-1)
            dl -= 1
        return '[' + ','.join(data) + ']'

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        data_strip = data.strip('[]')
        if not data_strip:
            return None
        data_list = data_strip.split(',')
        if not data_list:
            return None
        root = TreeNode(data_list[0])
        data_list.pop(0)
        que = [root]
        while data_list and que:
            new_que = []
            for x in que:
                if x:
                    left_val = data_list.pop(0) if data_list else None
                    left = TreeNode(left_val) if left_val and left_val != 'null' else None
                    x.left = left
                    if left:
                        new_que.append(left)
                    right_val = data_list.pop(0) if data_list else None
                    right = TreeNode(right_val) if right_val and right_val != 'null' else None
                    x.right = right
                    if right:
                        new_que.append(right)
            que = new_que
        return root


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

def print_tree(rt, dep=0):
    if rt is None:
        return
    print_tree(rt.left, dep + 1)
    print(' ' * dep, rt.val)
    print_tree(rt.right, dep + 1)


def op1():
    codec = Codec()
    root = TreeNode(1)
    n2 = TreeNode(2)
    n3 = TreeNode(3)
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    root.left = n2
    root.right = n3
    n3.left = n4
    n3.right = n5
    ss = codec.serialize(root)
    print(ss)
    tree = codec.deserialize(ss)
    print(tree)
    print_tree(tree)
    print_tree(codec.deserialize('[]'))


def op2():
    codec = Codec()

    root = TreeNode(1)
    n2 = TreeNode(2)
    root.left = n2

    print(codec.serialize(root))

    print_tree(codec.deserialize(codec.serialize(root)))


def main():
    op1()
    op2()


if __name__ == '__main__':
    main()
